# 有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。 
# 
#  现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 lef
# t 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。 
# 
#  求所能获得硬币的最大数量。 
# 
#  说明: 
# 
#  
#  你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。 
#  0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100 
#  
# 
#  示例: 
# 
#  输入: [3,1,5,8]
# 输出: 167 
# 解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
#      coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
#  
#  Related Topics 分治算法 动态规划 
#  👍 510 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


# todo 动态规划，有点绕，也好理解，官方题解可看懂
class Solution:
    def maxCoins(self, nums: List[int]) -> int:

        def dfs(nums, left, right):
            # 因为区间两边都不包含（思考为什么不包含）
            if left >= right-1:
                return 0

            # 如果已经计算过了
            if dp[left][right] != -1:
                return dp[left][right]

            for i in range(left + 1, right):
                sum = nums[left] * nums[i] * nums[right]
                sum += dfs(nums, left, i) + dfs(nums, i, right)

                dp[left][right] = max(dp[left][right], sum)

            return dp[left][right]

        n = len(nums)
        vals = [0 for _ in range(0, n + 2)]
        for j in range(1, n + 1):
            vals[j] = nums[j - 1]

        vals[0] = vals[n + 1] = 1

        dp = [[-1 for _ in range(0, n+2)] for _ in range(0, n+2)]

        return dfs(vals, 0, n + 1)

        # leetcode submit region end(Prohibit modification and deletion)


print(Solution().maxCoins([3, 1, 5, 8]))
